/**
 * 二维数组有X、Y和点
 * 对所有的i/j，问(0,0)到(i,j)的矩形中，X和Y数量相等且不为零的矩形有多少个 
 * 显然做一个二维前缀和的计数器即可
 */
class Solution {
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> X(n, vector<int>(m, 0));
        vector<vector<int>> Y(n, vector<int>(m, 0));

        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(0 == i){
                    if(0 == j){
                        switch(grid[i][j]){
                            case 'X': X[0][0] = 1; break;
                            case 'Y': Y[0][0] = 1; break;
                        }
                    }else{
                        X[0][j] = X[0][j - 1];
                        Y[0][j] = Y[0][j - 1];
                        switch(grid[i][j]){
                            case 'X': X[0][j] += 1; break;
                            case 'Y': Y[0][j] += 1; break;
                        }
                    }
                }else{
                    if(0 == j){
                        X[i][j] = X[i - 1][j];
                        Y[i][j] = Y[i - 1][j];
                        switch(grid[i][j]){
                            case 'X': X[i][0] += 1; break;
                            case 'Y': Y[i][0] += 1; break;
                        }
                    }else{
                        X[i][j] = X[i - 1][j] + X[i][j - 1] - X[i - 1][j - 1];
                        Y[i][j] = Y[i - 1][j] + Y[i][j - 1] - Y[i - 1][j - 1];
                        switch(grid[i][j]){
                            case 'X': X[i][j] += 1; break;
                            case 'Y': Y[i][j] += 1; break;
                        }
                    }
                }
            }
        }

        int ans = 0;
        for(int i=0;i<n;++i)for(int j=0;j<m;++j){
            if(X[i][j] and X[i][j] == Y[i][j]){
                ++ans;
            } 
        }
        return ans;
    }
};